package com.tgy.programmer_code_interview_guide._03_binarytree;


import com.tgy.leetcode.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

class UnionFindSet{

    private Map<TreeNode,TreeNode> parents;
    private Map<TreeNode,Integer> ranks;

    public UnionFindSet(TreeNode root) {

        parents = new HashMap<>();
        ranks = new HashMap<>();

        init(root);
    }

    private void init(TreeNode node) {

        if (node == null) {
            return;
        }

        parents.put(node,node);
        ranks.put(node,0);
        init(node.left);
        init(node.right);
    }

    public TreeNode find(TreeNode node) {

        /**
         *     1
         *    /  \
         *   2    3
         *
         *
         */
        TreeNode parentNode = parents.get(node);
        if (parentNode != node) {

            parentNode = find(parentNode);
            parents.put(node,parentNode);
        }

        return parentNode;
    }

    public void union(TreeNode n1,TreeNode n2) {

        if (n1 == n2) {
            return;
        }

        if (n1 == null || n2 == null) {
            return;
        }

        TreeNode p1 = find(n1);
        TreeNode p2 = find(n2);

        if (p1 == p2) {
            return;
        }

        Integer rank01 = ranks.get(p1);
        Integer rank02 = ranks.get(p2);

        if (rank01 < rank02) {

            parents.put(p1,p2);
        }else if (rank01 > rank02) {

            parents.put(p2,p1);
        }else {

            parents.put(p1,p2);
            ranks.put(p2,rank02 + 1);
        }
    }
}

class Query{

    private TreeNode firstNode;
    private TreeNode secondNode;


    public Query(TreeNode firstNode, TreeNode secondNode) {
        this.firstNode = firstNode;
        this.secondNode = secondNode;
    }

    public TreeNode getFirstNode() {
        return firstNode;
    }

    public TreeNode getSecondNode() {
        return secondNode;
    }
}

class CommonParent{

    /**
     * node -> node01,node02
     *
     */
    private Map<TreeNode, List<TreeNode>> queryMap;
    private Map<TreeNode,List<Integer>> indexMap;
    private UnionFindSet unionFindSet;
    private Map<TreeNode,TreeNode> commonParentSet;

    private TreeNode[] res;

    public CommonParent(TreeNode root, Query[] queries) {

        res = new TreeNode[queries.length];
        init(root,queries);
    }

    private void init(TreeNode root,Query[] queries) {

        commonParentSet = new HashMap<>();
        // 初始化unionFindSet
        unionFindSet = new UnionFindSet(root);

        // 初始化queryMap
        queryMap = new HashMap<>();
        indexMap = new HashMap<>();

        for (int i = 0; i < queries.length; i++) {

            Query query = queries[i];

            if (query.getFirstNode() == query.getSecondNode() || query.getFirstNode() == null) {

                res[i] = query.getSecondNode();
                continue;
            }

            if (query.getSecondNode() == null) {

                res[i] = query.getFirstNode();
                continue;
            }

            List<TreeNode> nodeList = queryMap.get(query.getFirstNode());

            if (nodeList == null) {
                nodeList = new LinkedList<>();
            }
            nodeList.add(query.getSecondNode());

            List<Integer> indexList = indexMap.get(query.getFirstNode());

            if (indexList == null) {

                indexList = new LinkedList<>();
            }
            indexList.add(i);
        }
    }

    private void addCommonParent(TreeNode node){

        if (node == null) {

            return;
        }

        addCommonParent(node.left);
        unionFindSet.union(node.left,node);
        commonParentSet.put(unionFindSet.find(node),node);
        addCommonParent(node.right);
        unionFindSet.union(node.right,node);
        commonParentSet.put(unionFindSet.find(node.right),node);

        List<TreeNode> treeNodes = queryMap.get(node);
        List<Integer> indexes = indexMap.get(node);

        for (int i = 0; i < treeNodes.size(); i++) {

            TreeNode treeNode = treeNodes.get(i);
            commonParentSet.containsKey(unionFindSet.find(treeNode));
        }

    }


}


public class _19_tarjan算法与并查集解决二叉树节点间的最近公共祖先 {


    public static void main(String[] args) {

        /**
         *                  6
         *
         *              3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
        t1.right.left = new TreeNode(9);
        t1.right.right = new TreeNode(10);

        UnionFindSet unionFindSet = new UnionFindSet(t1);
        unionFindSet.union(t1.left.left,t1.right.left);

        unionFindSet.find(t1.right.left);
    }
}
